package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度:O(N)
空间复杂度:O(N)
*/

func longestWPI(hours []int) int {
	arr := make([]int, len(hours))
	for i, v := range hours {
		if v > 8 {
			arr[i] = 1
		} else {
			arr[i] = -1
		}
	}

	// 构建前缀和,这里最前面必须要留一个为0的元素
	// 因为preSum[i]>0也就满足条件的，不一定要preSum[j]-preSum[i]
	// 前面留一个0，就会形成preSum[i]-preSum[0] = preSum[i]
	// 也就是说当i为0时，preSum[j]-preSum[i]就等于preSum[i]
	preSum := make([]int, len(hours)+1)
	for i := 1; i < len(arr)+1; i++ {
		preSum[i] = preSum[i-1] + arr[i-1]
	}

	// 我们要求满足arr[i+1..j]的sum>0的最大长度,其实就相当于preSum[j]-preSum[i]>0的最大长度(i<j);
	// 或者preSum[i] > 0 时[0~i]的最大长度,由于在preSum中最右边添加了一个0，所以只需要考虑preSum[j]-preSum[i]的情况
	// 因为preSum[j]-preSum[0]=preSum[j](当preSum[j]>0时长度就是j)
	// 那么可以套用962. 最大宽度坡.go，即求i<j且preSum[j]>preSum[i]的最大长度
	stack := make([]int, 0)
	// 构建单调递减栈
	for i, v := range preSum {
		if len(stack) == 0 || v < preSum[stack[len(stack)-1]] {
			stack = append(stack, i)
		}
	}

	// 从右往左遍历，如果当前元素cur>栈顶元素，则出栈,计算宽度坡
	ans := 0
	for i := len(preSum) - 1; i > 0; i-- {
		for len(stack) > 0 && preSum[i] > preSum[stack[len(stack)-1]] {
			pos := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans = Max(ans, i-pos)
		}
	}
	return ans
}
